/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年06月16日
*   描    述：
*
================================================================*/

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
} TreeNode;

// 定义队列节点结构，用于BFS
typedef struct QueueNode {
  TreeNode *node;
  int depth;
  struct QueueNode *next;
} QueueNode;

// 创建一个新的二叉树节点
TreeNode *createNode(int val) {
  TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
  if (newNode == NULL) {
    perror("Failed to allocate memory");
    exit(EXIT_FAILURE);
  }
  newNode->val = val;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}

// 释放二叉树节点的内存
void freeTree(TreeNode *root) {
  if (root == NULL) return;
  freeTree(root->left);
  freeTree(root->right);
  free(root);
}

// 入队操作
void enqueue(QueueNode **head, TreeNode *node, int depth) {
  QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
  if (newNode == NULL) {
    perror("Failed to allocate memory");
    exit(EXIT_FAILURE);
  }
  newNode->node = node;
  newNode->depth = depth;
  newNode->next = NULL;

  if (*head == NULL) {
    *head = newNode;
  } else {
    QueueNode *temp = *head;
    while (temp->next) {
      temp = temp->next;
    }
    temp->next = newNode;
  }
}

// 出队操作
QueueNode *dequeue(QueueNode **head) {
  if (*head == NULL) {
    return NULL;
  }
  QueueNode *temp = *head;
  *head = (*head)->next;
  return temp;
}

// 计算二叉树的最大深度（迭代方法）
int maxDepth(TreeNode *root) {
  if (root == NULL) {
    return 0;
  }

  QueueNode *queue = NULL;
  enqueue(&queue, root, 1);
  int maxDepth = 0;

  while (queue) {
    QueueNode *current = dequeue(&queue);
    TreeNode *node = current->node;
    int depth = current->depth;
    if (depth > maxDepth) {
      maxDepth = depth;
    }
    if (node->left) {
      enqueue(&queue, node->left, depth + 1);
    }
    if (node->right) {
      enqueue(&queue, node->right, depth + 1);
    }
    free(current);
  }

  return maxDepth;
}

int main() {
  //            1
  //          /   \
  //         2     3
  //        / \   / \
  //       4   5 6   7
  //      / \
  //     8   9
  struct TreeNode *root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  root->left->left->left = createNode(8);
  root->left->left->right = createNode(9);

  printf("maxDepth:%d", maxDepth(root));

  // 释放二叉树节点的分配内存
  freeTree(root);

  return 0;
}
